package reda.trees;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;






public class BSTPrinter {
	
	
	public BSTPrinter(){
		
	}
	
	
	/*
	 * a binary tree
	 * print(int i, int level,int order)
	 * 
	 * 
	 */
	
	public void print(int elm, int level, int order){
		
	}
	public ArrayList<Integer> getDetailledArray(Node root){
		ArrayList<Integer> printArr= new ArrayList<Integer>(); 
		Queue<Node> q1 = new LinkedList<Node>();
		Queue<Node> q2 = new LinkedList<Node>();
		if (root == null)
	        return printArr;
		 q1.clear();
		 q1.add(root);
		 q2.clear();
	
		 printArr.add(root.value);
		 printArr.add(-2);
		    while(!q1.isEmpty()||!q2.isEmpty()){
		    	if(q2.isEmpty()){
		    		 while(!q1.isEmpty()){
				        Node node = q1.remove();
				       
				        if(node.left != null) {
				        	q2.add(node.left);
				        	printArr.add(node.left.value);
				        }else{
				        	printArr.add(-1);
				        }
				        if(node.right != null){
				        	q2.add(node.right);
				        	printArr.add(node.right.value);
				        }else{
				        	printArr.add(-1);
				        }
		    		 }
		    	}
		    	
		    	printArr.add(-2);
		    	if(q1.isEmpty()){
		    		 while(!q2.isEmpty()){
				        Node node = q2.remove();
				       
				        if(node.left != null) {
				        	q1.add(node.left);
				        	printArr.add(node.left.value);
				        }else{
				        	printArr.add(-1);
				        }
				        if(node.right != null){
				        	q1.add(node.right);
				        	printArr.add(node.right.value);
				        }else{
				        	printArr.add(-1);
				        }
		    		 }
		    	}
		    
		    	printArr.add(-2);
		    }
		    return printArr;
	}
	
	
	
	public void printFromArray(Node root, ArrayList<Integer> printArr) {
		int size = printArr.size();
		
		int maxHight = getMaxLevel(root);
		int currLevel = 0;
		//parameter to fix spaces in same level
		int levelSpace = 1;
		int coneSpace = 1;
		int leftSpace = getLeftSpace(currLevel, maxHight)+(maxHight-currLevel);
		System.out.println("leftSpace:" + leftSpace);
		for(int ii=0;ii<= leftSpace;ii++){
			System.out.print(" ");
		}
		System.out.print(printArr.get(0));
	   // level++;
		boolean firstInLine = false;
		for (int i=1;i<=size-1;i++){
			
			if(printArr.get(i)==-2){
				System.out.println();
				//print the connectors /\...
		    		for(int j=1;j<=(Math.pow(2, maxHight-currLevel-1));j++){
		    			for(int l=0;l<=(Math.pow(2, currLevel)-1);l++){	
		    				if(l==0){
				 				for(int ii=0;ii<=leftSpace-j;ii++){
				 					System.out.print(" ");
				 				}
		    				}
			 				System.out.print("/");
			 				for (int k = 0;k<=j-1;k++){
				 					System.out.print(" ");
				 					System.out.print(" ");	 		
			 				}
			 				System.out.print("\\");
			 				if(coneSpace%2!=0){
				 				for(int ii=0;ii<=2*(Math.pow(2,(maxHight-currLevel))-j);ii++){
				 					System.out.print(" ");
				 				}
			 				}else{
			 					for(int ii=0;ii<=2*(Math.pow(2,(maxHight-currLevel-1))-j);ii++){
				 					System.out.print(" ");
				 				}
			 				}
			 				coneSpace++;
		    			}
		    			System.out.println();
		 	        }
		    		
		    	
				
				currLevel++;
				leftSpace = getLeftSpace(currLevel, maxHight)+(maxHight-currLevel);
				firstInLine = true;
				levelSpace = 1;
			}
			else{
				if(firstInLine){
		 			for(int ii=0;ii<=leftSpace;ii++){
		 					System.out.print(" ");
		 			}  
		    		
				}else{
					if(levelSpace%2==0){
		    			for(int ii=0;ii<=2*(Math.pow(2,(maxHight-currLevel)));ii++){
		 					System.out.print(" ");
		 				}
					}
					else{
		    			for(int ii=0;ii<=2*(Math.pow(2,(maxHight-currLevel-1)));ii++){
		 					System.out.print(" ");
		 				}
					}
				}
				System.out.print(printArr.get(i)+" ");
				firstInLine = false;
				levelSpace++;
				coneSpace=1;
			}
		}
	}
	
	
	

	public void printByLevel(Node root){
		ArrayList<Integer> printArr= new ArrayList<Integer>(); 
		Queue<Node> q1 = new LinkedList<Node>();
		Queue<Node> q2 = new LinkedList<Node>();
		if (root == null)
	        return;
		 q1.clear();
		 q1.add(root);
		 q2.clear();
	
		 printArr.add(root.value);
		 printArr.add(-2);
		    while(!q1.isEmpty()||!q2.isEmpty()){
		    	if(q2.isEmpty()){
		    		 while(!q1.isEmpty()){
				        Node node = q1.remove();
				        System.out.print(node.value + " ");
				        if(node.left != null) {
				        	q2.add(node.left);
				        	printArr.add(node.left.value);
				        }else{
				        	printArr.add(-1);
				        }
				        if(node.right != null){
				        	q2.add(node.right);
				        	printArr.add(node.right.value);
				        }else{
				        	printArr.add(-1);
				        }
		    		 }
		    	}
		    	System.out.println();
		    	printArr.add(-2);
		    	if(q1.isEmpty()){
		    		 while(!q2.isEmpty()){
				        Node node = q2.remove();
				        System.out.print(node.value + " ");
				        if(node.left != null) {
				        	q1.add(node.left);
				        	printArr.add(node.left.value);
				        }else{
				        	printArr.add(-1);
				        }
				        if(node.right != null){
				        	q1.add(node.right);
				        	printArr.add(node.right.value);
				        }else{
				        	printArr.add(-1);
				        }
		    		 }
		    	}
		    	System.out.println();
		    	printArr.add(-2);
		    }
		    System.out.println("end");
		   
		//    printFromArray(root, printArr);
		
		    
		    
	}
	
	
	
	
	
	private int getLeftSpace(int currLevel, int maxHeight ){
		int n = maxHeight - currLevel;
		if (n<=1)
			return 1;
		int sum = 1;
		for(int i= 1; i<n;i++)
			sum += Math.pow(2, i);
		
		return sum;	
			//return (n*(n+1))/2;
		
	}
	
	private int getMaxLevel(Node root){
			
		if (root==null)
			return 0;
					
		return 1+Math.max(getMaxLevel(root.right), getMaxLevel(root.left));
	}
			
	public int getLeftWidth(Node root){
		int wleft = 0;
		Node temp = root;
		while(temp!= null){
			wleft++;
			temp=temp.left;
		}
		return wleft;
			
	}
	
	
	
}
